package com.example.datastruct;

import com.sun.org.apache.regexp.internal.RE;

import java.util.Scanner;

public class RBTree<k extends Comparable<k>,v>{

    private static final boolean RED =false;
    private static final boolean BLACK = true;
    private RBNode root;

    public static void main(String[] args) {
       Animal a  =new AnimalSmall();

        Scanner scanner = new Scanner(System.in);
        RBTree<String,Object> rbt = new RBTree<>();

        while(true){
            System.out.println("请输入要插入的节点:");

            String key = scanner.next();
            System.out.println();

            if(key.length() ==1) {
                key = "00"+key;
            }else if(key.length() ==2 ){
                key = "0" + key;
            }
            rbt.put(key,null);

        }

    }
    public RBNode getRoot() {
        return root;
    }

    public void setRoot(RBNode root) {
        this.root = root;
    }

    /**
     * 左旋实现
     *      p               pr
     *     /\              /\
     *    pl pr   ==>     p  rr
     *      /\           /\
     *     rl rr        pl rl
     *
     *  左旋的时候
     *  p-pl 和 r-rr 不变
     *  pr-pl变为 p-rl
     *  判断 p节点有没有父节点
     *   如果没有
     *     pr为root节点
     *   如果有
     *     pr.parent = p.parent
     *   还要设置pr 为 p.parent的左右子节点
     *
     *   最后设置
     *   p-pr 为pr-p
     */
    private void leftRotate(RBNode p){
        //节点不能为空
        if(p!= null){

            final RBNode r = p.right;
            //1.pr-rl变为p-rl
            p.right= r.left;

            if(r.left != null) {
                r.left.parent = p;
            }
            //判断p 是否有父节点
            r.parent = p.parent;
            if(p.parent == null) {
                root=r;
            }else if(p.parent.left ==p ){
                p.parent.left=r;
            }else{
                p.parent.right=r;
            }
            //最后设置 p 为 r的左子节点
            r.left=p;
            p.parent=r;

        }

    }



    private void rightRotate(RBNode p){
        //节点不能为空
        if(p!= null){

            final RBNode r = p.left;
            //1.pr-rl变为p-rl
            p.left= r.right;

            if(r.right != null) {
                r.right.parent = p;
            }
            //判断p 是否有父节点
            r.parent = p.parent;
            if(p.parent == null) {
                root=r;
            }else if(p.parent.left ==p ){
                p.parent.left=r;
            }else{
                p.parent.right=r;
            }
            //最后设置 p 为 r的左子节点
            r.right=p;
            p.parent=r;

        }

    }

    /**
     * 新增节点
     * 红黑树节点的新增
     *   1 普通的二叉树的插入
     *        先查询到插入的位置
     *        将kv 封装为Node对象 插入到Tree钟
     *   2 红黑树的平衡(调整  旋转+变色)
     * @param key
     * @param value
     */
    public void put(k key,v value){
        RBNode t =this.root;
        if(t==null){
            //说明红黑树是空的，插入的就是root节点
            root = new RBNode(null,key,value == null ? key :value);
            setColor(root,BLACK);
            return;
        }
        //查找插入的位置
        int cmp;
        // 记录寻找节点的父节点
        RBNode parent;
        if(key == null) {
            throw new NullPointerException();
        }

        do{
            parent = t;
            cmp = key.compareTo((k) t.key);

            if(cmp <0) {
                t = t.left;
            }else if(cmp > 0){
                t = t.right;
            }else{
                t.setValue(value == null?key:value);
                return;
            }
        }while(t !=null);

        //表示找到了插入的位置 parent的子节点
        RBNode e = new RBNode(parent,key,value==null ? key:value);
        if(cmp < 0){
            parent.left = e;
        }else{
            parent.right =e;
        }

        // 做平衡处理 旋转,变色
        fixAfterPut(e);
    }

    /**
     * 红黑树平衡的调整处理
     * 1 2-3-4树 2节点新增一个元素  直接合并为3节点
     *    红黑树：新增一个红色节点  这个红色节点会添加到黑色节点下：不需要调整
     * 2 2-3-4树 3节点新增一个元素 合并为一个4节点
     *    红黑树: 会有6种情况 两种（左中右）的不需要调整
     *            根左左  根右右  旋转一次
     *            根左右  根右左  旋转两次
     * 3 2-3-4树 4节点新增一个元素 4节点中间元素升级为父节点，新增元素和剩下节点合并
     *   红黑树： 新增节点是红色+爷爷节点是黑色  父节点和叔叔节点为红色 调整为
     *       爷爷节点变为红色 父亲和叔叔节点变为黑色  如果爷爷节点为root节点 则调整为黑色
     * @param e
     */
    private void fixAfterPut(RBNode e) {
        //插入的节点都为红色节点
        setColor(e,RED);

        while (e != null && e != root && parentOf(e).color == RED){
            //1 e的父节点是e的爷爷的左子节点  4种需要处理的情况
            if(parentOf(e) == parentOf(parentOf(e)).left) {
                //满足跳的四种情况 根据是否有叔叔节点又一分为二处理

                //获取当前节点的叔叔节点
                RBNode y = rightOf(parentOf(e));
                if (colorOf(y) == RED){
                    //说明叔叔节点存在，那就是满足条件3的情况
                    setColor(parentOf(e),BLACK);
                    setColor(y,BLACK);
                    setColor(parentOf(parentOf(e)),RED);

                    //递归处理
                    e = parentOf(parentOf(e));
                }else{
                    //情况2
                    if(e == rightOf(parentOf(e))) {
                        //插入节点的是父节点的右侧节点 我们需要先根据父节点做一次左旋
                        e = parentOf(e);
                        leftRotate(e);
                    }

                    setColor(parentOf(e),BLACK);
                    setColor(parentOf(parentOf(e)),RED);
                    //根据爷爷节点做 右旋操作
                    rightRotate(parentOf(e));
                }
            }else{
                //与上面正好相反


                //满足跳的四种情况 根据是否有叔叔节点又一分为二处理

                //获取当前节点的叔叔节点
                RBNode y = leftOf(parentOf(e));
                if (colorOf(y) == RED){
                    //说明叔叔节点存在，那就是满足条件3的情况
                    setColor(parentOf(e),BLACK);
                    setColor(y,BLACK);
                    setColor(parentOf(parentOf(e)),RED);

                    //递归处理
                    e = parentOf(parentOf(e));
                }else{
                    //情况2
                    if(e == leftOf(parentOf(e))) {
                        //插入节点的是父节点的右侧节点 我们需要先根据父节点做一次左旋
                        e = parentOf(e);
                        rightRotate(e);
                    }

                    setColor(parentOf(e),BLACK);
                    setColor(parentOf(parentOf(e)),RED);
                    //根据爷爷节点做 右旋操作
                    leftRotate(parentOf(e));
                }

            }
        }

        //根节点都为黑色节点
        setColor(root,BLACK);
    }

    private boolean colorOf(RBNode node){
        return node == null ? BLACK:node.color;
    }

    private RBNode parentOf(RBNode node){
        return node != null ?node.parent:null;
    }

    private RBNode leftOf(RBNode node){
        return node!=null ? node.left : null;
    }

    private RBNode rightOf(RBNode node) {
        return node != null ? node.right :null;
    }

    private void setColor(RBNode node,boolean color) {
        if(node!= null) {
            node.setColor(color);
        }
    }


    /**
     * 查找node节点的前驱节点
     * 定义：   后续节点  一个结点的后继，是大于x.key的最小关键字的结点。
     *            前驱节点  一个结点的前驱，是小于x.key的最大关键字的结点。
     * @param node
     * @return
     */
    private RBNode predecessor(RBNode node){

        if(node == null){
            return null;
        }else if(node.left != null){

            RBNode p = node.left;

            while (p.right != null) {
                p = p.right;
            }
            return p;
        }else{
            //这种情况在删除钟是不会存在的，但是 就前驱和后继节点的情况来说还是会存在的
            RBNode p = node.parent;
            RBNode ch = node;
            while(p != null && ch==p.left){
                ch = p;
                p = p.parent;
            }
            return p;
        }

    }



    /**
     * 查找node节点的后继节点
     * 定义：   后续节点  一个结点的后继，是大于x.key的最小关键字的结点。
     *            前驱节点  一个结点的前驱，是小于x.key的最大关键字的结点。
     * @param node
     * @return
     */
    private RBNode sccessor(RBNode node){

        if(node == null){
            return null;
        }else if(node.right != null){

            RBNode p = node.right;

            while (p.left != null) {
                p = p.left;
            }
            return p;
        }else{
            //这种情况在删除钟是不会存在的，但是 就前驱和后继节点的情况来说还是会存在的
            RBNode p = node.parent;
            RBNode ch = node;
            while(p != null && ch==p.right){
                ch = p;
                p = p.parent;
            }
            return p;
        }

    }

    /**
     * 删除节点
     * @param key
     * @return
     */
    public v remove(k key){
        //先根据key 找到对应的节点
        RBNode node = getNode(key);
        if(node == null) {
            return null;
        }
        //把删除节点原来的值保存下来
        v oldValue = (v) node.value;

        //删除节点的方法
        deleteNode(node);
        return oldValue;
    }

    /**
     * 删除节点
     * 3种情况
     *  1 删除叶子节点 直接删除
     *  2 删除节点有一个子节点，用子节点来替代
     *  3 删除的节点有2个子节点，此时我们需要获取对应的前驱或者后继节点来替代
     *    可以转换为1、2的情况
     * @param node
     */
    private void deleteNode(RBNode node){
        // 情况3 有左右子节点，然后转换为1 2 的情况处理
        if(leftOf(node) != null && rightOf(node) !=null) {
            //找到要删除节点的后继节点
            RBNode sccessor = this.sccessor(node);
            //然后用后继节点的值 覆盖掉要删除节点的信息
            node.key = sccessor.key;
            node.value = sccessor.value;
            //然后我们要删除的节点就变为 后继节点
            node = sccessor;
        }

        //获取要替换的节点
        RBNode replacement = node.left != null  ? node.left : node.right;

        if(replacement != null) {
            //情况2:删除有一个子节点的情况
            replacement.parent = node.parent;
            if(node.parent == null) {
                root = replacement;
            }else if(node == leftOf(parentOf(node))) {
                parentOf(node).left = replacement;
            }else{
                parentOf(node).right = replacement;
            }
            //将node节点的左右孩子和父指针都指向null.node等待GC
            node.left=node.right=node.parent =null;
            //替换完成后 需要调整平衡
            if(node.color == BLACK) {
                fixAfterRemove(replacement);
            }
        }else if (node.parent == null){
            root = null;
        }else{
            //情况1 删除的就是一个叶子节点 直接删除
            //先调
            if(node.color == BLACK) {
                fixAfterRemove(node);
            }
            //再删除
            if(node.parent != null){
                if(node == leftOf(parentOf(node))){
                    parentOf(node).left = null;
                }else{
                    parentOf(node).right = null;
                }
                node = null;
            }
        }
    }

    /**
     * 删除后的调整处理
     * 2-3-4树 删除操作
     *  1.情况1：自己能搞定，对应的叶子节点是3节点或者4节点
     *  2.情况2: 自己搞不定，需要兄弟节点借，但是兄弟节点不借用，找父亲节点借，父亲下来，然后兄弟结点找一个人代替父亲当家
     *  3.情况3: 跟兄弟节点借;兄弟也没有
     * @param x
     */
    private void fixAfterRemove(RBNode x){
        //情况2 和3
        while (x !=root && colorOf(x) == BLACK){
            if(x == leftOf(x)){
                //查找兄弟节点
                RBNode rbNode = rightOf(parentOf(x));
                if(colorOf(rbNode) == RED) {
                    //不是真正的兄弟节点
                    setColor(rbNode,BLACK);
                    setColor(parentOf(x),RED);

                    leftRotate(parentOf(x));
                    rbNode = rightOf(parentOf(x));
                }

                if(colorOf(leftOf(rbNode)) == BLACK && colorOf(rightOf(rbNode)) ==BLACK){
                    //情况3 跟兄弟借 兄弟节点没得借
                    setColor(rbNode,RED);
                    x = parentOf(x);
                }else{
                    //情况2 跟兄弟借 兄弟节点有借

                    if(colorOf(rightOf(rbNode)) ==BLACK) {
                        //不存在右孩子，那么肯定存在左孩子
                        setColor(rbNode,RED);
                        setColor(leftOf(rbNode),BLACK);
                        rightRotate(rbNode);
                        rbNode = rightOf(parentOf(x));
                    }

                    setColor(rbNode,colorOf(x));
                    setColor(parentOf(x),BLACK);
                    setColor(rightOf(rbNode),BLACK);
                    leftRotate(parentOf(x));
                    x = root;
                }

            }else{
            //查找兄弟节点
                RBNode rbNode = leftOf(parentOf(x));
                if(colorOf(rbNode) == RED) {
                    //不是真正的兄弟节点
                    setColor(rbNode,BLACK);
                    setColor(parentOf(x),RED);

                    rightRotate(parentOf(x));
                    rbNode = leftOf(parentOf(x));
                }

                if(colorOf(rightOf(rbNode)) == BLACK && colorOf(leftOf(rbNode)) ==BLACK){
                    //情况3 跟兄弟借 兄弟节点没得借
                    setColor(rbNode,RED);
                    x = parentOf(x);
                }else{
                    //情况2 跟兄弟借 兄弟节点有借

                    if(colorOf(leftOf(rbNode)) ==BLACK) {
                        //不存在右孩子，那么肯定存在左孩子
                        setColor(rbNode,RED);
                        setColor(rightOf(rbNode),BLACK);
                        leftRotate(rbNode);
                        rbNode = leftOf(parentOf(x));
                    }

                    setColor(rbNode,colorOf(x));
                    setColor(parentOf(x),BLACK);
                    setColor(leftOf(rbNode),BLACK);
                    rightRotate(parentOf(x));
                    x = root;
                }
            }
        }
        //情况1:替代的节点是红色，直接设置为黑色即可
        setColor(x,BLACK);
    }

    /**
     * 根据key 获取对应的节点
     * @param key
     * @return
     */
    private RBNode getNode(k key) {
        RBNode node = this.root;
        while(node!= null) {
            int cmp = key.compareTo((k) node.key);
            if(cmp < 0) {
                node = node.left;
            }else if(cmp >0){
                node = node.right;
            }else{
                return  node;
            }
        }
        return null;
    }

    //节点类型
    static class RBNode<k extends Comparable<k>, v> {
        private RBNode parent;
        private RBNode left;
        private RBNode right;

        private boolean color;
        private k key;
        private v value;

        public RBNode(RBNode parent, RBNode left, RBNode right, boolean color, k key, v value) {
            this.parent = parent;
            this.left = left;
            this.right = right;
            this.color = color;
            this.key = key;
            this.value = value;
        }

        public RBNode(RBNode parent, k key, v value) {
            this.parent = parent;
            this.key = key;
            this.value = value;
        }

        public RBNode() {
        }

        public RBNode getParent() {
            return parent;
        }

        public void setParent(RBNode parent) {
            this.parent = parent;
        }

        public RBNode getLeft() {
            return left;
        }

        public void setLeft(RBNode left) {
            this.left = left;
        }

        public RBNode getRight() {
            return right;
        }

        public void setRight(RBNode right) {
            this.right = right;
        }

        public boolean isColor() {
            return color;
        }

        public void setColor(boolean color) {
            this.color = color;
        }

        public k getKey() {
            return key;
        }

        public void setKey(k key) {
            this.key = key;
        }

        public v getValue() {
            return value;
        }

        public void setValue(v value) {
            this.value = value;
        }
    }
}
